class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.empty()) return 0;
        
        int n = heights.size();
        vector<int> leftBound(n), rightBound(n);
        
        leftBound[0] = -1;
        for (int i = 1; i < n; i++) {
            int p = i - 1;
            while (p >= 0 && heights[p] >= heights[i]) {
                p = leftBound[p]; 
            }
            leftBound[i] = p;
        }
        
        rightBound[n-1] = n;
        for (int i = n-2; i >= 0; i--) {
            int p = i + 1;
            while (p < n && heights[p] >= heights[i]) {
                p = rightBound[p]; 
            }
            rightBound[i] = p;
        }
        
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            int width = rightBound[i] - leftBound[i] - 1;
            maxArea = max(maxArea, heights[i] * width);
        }
        
        return maxArea;
    }
};                          //法1：海水涨潮思路



class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.empty()) return 0;
        
        int maxArea = 0;
        stack<int> st; 
        
        for (int i = 0; i < heights.size(); i++) {
 
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int height = heights[st.top()];
                st.pop();

                int width = st.empty() ? i : i - st.top() - 1;
                
                maxArea = max(maxArea, height * width);
            }
            st.push(i);
        }
        
        // 处理栈中剩余的柱子
        while (!st.empty()) {
            int height = heights[st.top()];
            st.pop();
            
            int width = st.empty() ? heights.size() : heights.size() - st.top() - 1;
            
            maxArea = max(maxArea, height * width);
        }
        
        return maxArea;
    }
};            //法2：单调递增栈